from tools_algorithm import *


class Solution:
    def earliestSecondToMarkIndices(
        self, nums: List[int], changeIndices: List[int]
    ) -> int:
        n, m = len(nums), len(changeIndices)

        def f(s):
            h = {}
            for i in range(s):
                h[changeIndices[i] - 1] = i
            p = 0
            cnt = 0
            for i in range(s):
                v = changeIndices[i] - 1
                if h[v] == i:
                    if p < nums[v]:
                        return False
                    p -= nums[v]
                    cnt += 1
                else:
                    p += 1

            return cnt == n

        ans = bisect_left(range(m + 1), True, key=f)
        return -1 if ans > m else ans
